/**
 * time->O(N*logN)
 * 任取待排序元素序列中的某元
 * 素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有
 * 元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
 */
public class QuickSort {
    // 假设按照升序对array数组中[left, right)区间中的元素进行排序
    void quickSort(int[] array, int left, int right) {
        if (right - left <= 1)
            return;
        // 按照基准值对array数组的 [left, right)区间中的元素进行划分
        int div = partition(array, left, right);
        // 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
        // 递归排[left, div)
        quickSort(array, left, div);
        // 递归排[div+1, right)
        quickSort(array, div + 1, right);
    }

    /**
     * 士兵法
     */
    private static int partition(int[] array, int left, int right) {
        int i = left;
        int j = right;
        int pivot = array[left];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            while (i < j && array[i] <= pivot) {
                i++;
            }
            swap(array, i, j);
        }
        swap(array, i, left);
        return i;
    }

    /**
     * 挖坑法
     */
    private static int partition1(int[] array, int left, int right) {
        int i = left;
        int j = right;
        int pivot = array[left];
        while (i < j) {
            while (i < j && array[j] >= pivot) {
                j--;
            }
            array[i] = array[j];
            while (i < j && array[i] <= pivot) {
                i++;
            }
            array[j] = array[i];
        }
        array[i] = pivot;
        return i;
    }


    public static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {8, 5, 8, 752, 4, 5, 8, 874, 55, 5, 874, 5, 5, 9, 952, 48, 6, 2, 5, 6, 32, 5, 6, 8};
        QuickSort q=new QuickSort();
        q.quickSort(arr,0, arr.length-1);
        for (int x :
                arr) {
            System.out.println(x);
        }
    }
}